// 公共祖先:https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=13&tqId=1024325&ru=%2Fpractice%2Fa861533d45854474ac791d90e447bafd&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
// 1.重点题目：把各种情况都考虑到即可；1.目标值在左子树与右子树上；2.目标值在左子树上，当前树没值；3.目标值在右子树上，当前树没值等等；
// 解决方式：自己实现

#include <vector>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution1 {
public:
    //记录是否找到到o的路径
    bool flag = false;
    //求得根节点到目标节点的路径
    void dfs(TreeNode* root, vector<int>& path, int o){
        if(flag || root == NULL)
            return;
        path.push_back(root->val);
        //节点值都不同，可以直接用值比较
        if(root->val == o){
            flag = true;
            return;
        }
        //dfs遍历查找
        dfs(root->left, path, o);
        dfs(root->right, path, o);
        //找到
        if(flag)
            return;
        //该子树没有，回溯
        path.pop_back();
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> path1, path2;
        //求根节点到两个节点的路径
        dfs(root, path1, o1);
        //重置flag，查找下一个
        flag = false;
        dfs(root, path2, o2);
        int res;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++){
            if(path1[i] == path2[i])
                //最后一个相同的节点就是最近公共祖先
                res = path1[i];
            else
                break;
        }
        return res;
    }
};

class Solution2 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if (root == nullptr) return -1;

        int res = -1;
        if (root ->val == o1 || root ->val == o2) {
            res = root->val;
        }

        int l1 = lowestCommonAncestor(root->left, o1,o2);
        int r1 = lowestCommonAncestor(root->right, o1,o2);
        if (l1 != -1 && r1 != -1) {
            return root->val;
        }
        if (l1 != -1 && res == -1) {
            return l1;
        }
        if (r1 != -1 && res == -1) {
            return r1;
        }

        return res;
    }
};